1. Field of the Invention
The present invention relates generally to communication networks, and more specifically to a method and apparatus for scheduling cells in queues for transmission in an asynchronous transfer mode (ATM) switch.
2. Related Art
Different types of communication networks have evolved in the past to provide different types of services. For example, voice networks allow users to converse in a telephone conversation and data networks allow users to share vast quantities of data. In general, each type of communication network can have different requirements for providing the corresponding services. As an illustration, voice networks may need predictable bandwidth with low latencies to support voice calls while data networks may need high bandwidth in bursts to support large data transfers.
Due to such varying requirements, different types of communication networks have evolved with separate communication backbones, possibly implemented with different technologies. Often, these different technologies are implemented using very different techniques or principles. For example, voice networks have been implemented using a technique commonly referred to as time division multiplexing, which provides fixed and predictable bandwidth for each voice channel. On the other hand, data networks (such as those based on Internet Protocol) have been implemented to share available bandwidth on demand. That is, any end-system of a data network can potentially use all the available bandwidth at a given instance of time, and then the other systems have all the bandwidth for use.
In general, having separate communication backbones for communication networks results in inefficiency in the usage of the overall bandwidth. According to the well-known principle of xe2x80x98economy of scalexe2x80x99, ten servers serving hundred customers of a single queue generally provide slower service than thousand servers serving ten thousand clients even though the server-client ratio is the same. There is more efficiency with larger numbers typically because any of the larger pool of available servers can immediately serve a customer in a queue, and thus keep the queue length short.
The inefficiency (due to separate communication backbones) can result in degradation of aggregate service levels or in inability to provide more services. The problem can be exasperated with the increasing demands being placed on the networks. In addition, the overhead to manage the separate networks may be unacceptably high due to the increased number of components in the overall system. Further, the same end-station can be providing different services, which have varying requirements. For example, a computer system may be used for diverse applications such as data sharing, telephone conversations, and video conferencing applications.
Accordingly, the communications industry has been migrating towards a shared communications backbone for all the different types of services. Asynchronous transfer mode (ATM) is one standard which allows such a shared communication backbone. In general, an ATM network includes several ATM switches connecting several end-systems. Each switch includes several ports to connect to end systems and other switches. A switch receives a cell on one port and forwards the cell on another port to provide a connection between (or among) the end-systems.
To communicate with another end-system, an end-station of a communication network usually xe2x80x98opens a connectionxe2x80x99. Opening a connection generally refers to determining a sequence of switches between the two end-stations such that the switches provide at least one communication path between the two end-stations with any specific service levels required for the communication. Once a connection is established, the end systems communicate with each other using cells in an ATM environment. The switches in the communication path receive cells on one port and forward the received cells on another port to support the connection.
Switches often maintain internal queues while transferring cells from one port to the other. The cells are buffered in the queues awaiting their turn for transmission. A scheduler determines the order of transmission of the queued cells according to a scheduling scheme. In one scheduling scheme, a queue is maintained for each connection, which provides the flexibility to serve each connection according to the specific service parameters (known as quality of service xe2x80x98QoSxe2x80x99 parameters) with which the connection may have been setup. The scheduler needs to schedule cells for transmission to meet these service requirements.
One such service requirement is fair scheduling. Fairness generally refers to proportional allocation of bandwidth to individual connections consistent with the QoS parameters associated with each connection. The QoS parameters can include, among others, a desired bandwidth and a priority for each connection. For example, assuming equal priority, cells belonging to a higher bandwidth connection may need to be transmitted more often than cells belonging to lower bandwidth connections independent of the order in which the cells of the connections may have arrived into the switch or at the output port during internal processing in the switch.
Another service requirement is xe2x80x98shapingxe2x80x99. Shaping refers to the provision of a specified maximum bandwidth (xe2x80x9cshaping ratexe2x80x9d) to a connection. Shaping provides the ability to restrict a connection from using more bandwidth than the shaping rate. Such restriction provides a network manager the ability to establish cost structures commensurate with the bandwidth a connection can use. In addition, shaping can prevent switches or end-systems down the connection path from being over-flooded with cells from the connection.
A scheduler may need to schedule cells of a connection while restricting the maximum bandwidth used by the connection to the shaping rate. The scheduling function may need to be performed without consuming undue amounts of memory space or processing power to avoid throughput performance bottlenecks in the switch. Therefore, what is needed is a scheduler which can shape a connection without requiring excessive memory or processing power.
In addition, a scheduler may need to support dynamic change of shaping rate. For example, if the ATM backbone is lightly congested, it may be desirable to increase the shaping rate of a connection. The level of congestion can be determined, for example, based on available bit rate (ABR) ATM service, which is communicated to other switches in a connection path.
Another feature which may enhance the acceptance of ATM technology is efficient support for transmission of frames. Frames typically refer to data packets sent by end-systems such as those in the Internet Protocol environment. A frame is usually broken into small cells suitable for transmission on ATM communications backbones, and reassembled before being delivered to the end-system. Accordingly, what is also needed is a scheduler which supports the efficient transmission of frames in an ATM backbone.
Yet another requirement may be that all the above service requirements and features may need to be supported in one integrated framework so that a switch can be designed to provide all the features. The framework needs to take into consideration what may appear as contradictory requirements. For example, when scheduling cells of a non-shaped connection, it is generally acceptable (and many times desirable) to provide more bandwidth than which is desired for the non-shaped connection. In contrast, the shaped connections need to be restricted from using more bandwidth than the shaping rate.
Therefore, what is also needed is an integrated framework which enables the provision of any of the desired features and services noted above as requested on a per-connection basis.
The present invention is directed to a flexible scheduler in a cell switch. The scheduler enables the cells of various connections to be scheduled fairly while providing for efficient shaping (or non-shaping) and frame transmission in an integrated framework. By providing all the feature in an integrated framework, the present invention simplifies the implementation of schedulers in accordance with the present invention. Fairness generally refers to proportional allocation of bandwidth to individual connections consistent with the QoS parameters associated with each connection.
In one embodiment, fairness is achieved by defining several groups of scheduling buckets for each port of a switch. Buckets can be implemented as a first-in-first-out (FIFO) queue using linked lists. Each group has an associated bandwidth range. A group serves connections having a bandwidth, which falls in the associated range.
Fairness can be maintained first at a group level, and then among connections within a group. That is, a group having connections with more aggregate bandwidth may be allocated more turns for transmission on a port than a group having connection with lesser aggregate bandwidth range. Similarly, within a group, a cells on a connection having a high desired bandwidth is provided more turns for transmission than cells on a connection having a low desired bandwidth.
Fairness can be maintained even when a connection is shaped or not shaped or whether the connection is transferring cells forming a frame as described below. In addition, the bandwidth allocated to each connection can also be dynamically varied as also described below.
For a group serving non-shaped connections, fairness is achieved by associating a bucket gap, which is inversely proportional to the desired bandwidth of a connection or proportional to the average intercell arrival time of the connection. When a cell of a connection is scheduled for transmission, the next cell in the connection is placed a number of buckets equal to the bucket gap away from the current bucket. A current bucket may be defined as a bucket from which cells are considered presently for transmission. Cells in a next bucket are considered for transmission only after transmitting all cells in a current bucket. Cells within a bucket can be transmitted in a FIFO scheme.
By allocating a cell to a bucket, the cell""s turn for transmission is defined to be after the turn of all cells in the intermediate buckets between the current bucket and the allocated bucket. Thus, the relative turn of a cell is defined by the bucket to which it is assigned, and the order of arrival within the bucket. As successive cells of a connection are assigned to buckets which are apart by bucket gap, connections with large bucket gaps are allocated lower bandwidth than connections with small bucket gaps. Accordingly, fairness is achieved among connections served by a group.
A connection can be shaped in the framework of above. Specifically, a connection is shaped by generally ensuring that any two successive cells of a connection do not depart with an intercell time of less than that determined by the shaping rate. Accordingly, a conformance time is computed for each cell of the connection. Conformance time represents the earliest time a corresponding cell may depart for transmission.
The conformance time is used to select a bucket for a cell by logically associating a bucket interval (i.e., defined by a start time coordinate and an end time coordinate) with each bucket. A cell may be placed in a bucket if the conformance time of the cell falls within the bucket interval of the bucket. Cells in buckets can be scheduled for transmission as in non-shaped connections (i.e., consider a next bucket only after all cells of the current bucket are scheduled for transmission, and FIFO scheme within a bucket), with the additional requirement that a cell is not allowed to depart for transmission until the corresponding conformance time is reached.
In one embodiment, the conformance time for each cell is computed by Equations
C(j)=MAX[E(j),A(j)]xe2x80x83xe2x80x83[Equation (1)]
E(j+1)=C(j)+Txe2x80x83xe2x80x83[Equation (2)]
wherein, C(j) represents the conformance time of a cell j, E(j) represents the expected arrival time of a cell j, A(j) represents the arrival time for cell j, and T represents the average intercell time for a queue for a desired shaping rate. The arrival time is defined as the time a cell is placed from a connection queue into a scheduling bucket. As the conformance time of a cell is at least as much as the conformance time of a previous cell plus the intercell time (T), cells depart with an interval of at least T. Accordingly, shaping is achieved. The shaping rate is defined by the intercell time T.
From Equations (1) and (2), it is noted that the computation of conformance time of a current cell requires the conformance time of a previous cell of the connection. Accordingly, the conformance time of the previous cell may be stored in an internal memory, and when the current cell needs to be scheduled, the stored conformance time is retrieved to compute the conformance time of the current cell.
Such storage requirement and computation requirement may not be acceptable in certain situations. Accordingly, such requirements may be avoided in accordance with an aspect of the present invention.
A close examination of Equations (1) and (2) reveals that conformance time of a previous cell is not required under certain situations. For example, assume that the bucket interval of a current bucket being processed (for departure by a scheduler) is at least intercell time (T) prior to a present time (real time). In such a situation, the conformance time of the newly arriving cell is equal to the arrival time (i.e., present time according to the definition above). Therefore, the conformance time of the previous cell may not be required if the scheduler is backlogged by more than the intercell time (T) of a connection. Accordingly, the conformance time of previous cells need not be stored according to an aspect of the present invention.
In addition, assuming that the connections in a given group have intercell times (Ts) smaller than a maximum intercell time (Tmax, corresponding to a connection with lowest shaping rate), the conformance time need not be maintained for cells in any buckets whose bucket interval is more than maximum intercell time prior to the present time. Cells in all such buckets may be placed in a different queue (frozen queue), and then scheduled for departure. The next cell in the same connection for any departing cell can be assigned a conformance time equal to the time of departure of the departing cell. Therefore, the conformance time of cells in the frozen queue need not be stored. Accordingly, the processing and memory requirements can be minimized when cells are backlogged in the internal queues (typically during congestion periods).
According to another aspect of the present invention the shaping rate of a shaped connection or the bandwidth allocated to a non-shaped connection can be varied dynamically. In the case of shaped connections, the intercell time (T) is changed to reflect the new shaping rate and conformance time of all cells on a corresponding connection queue (not yet placed in a bucket) is computed using the new intercell time. Cells are placed in buckets (possibly in new groups) and transmitted according to the conformance time computed using the new intercell time. Out-of-sequence delivery problems are avoided as only the head cell (first cell awaiting transmission) of each connection is placed in a bucket. Accordingly, the connection is shaped with the new (changed) shaping rate.
For non-shaped queues the bucket gap is changed to correspond to the new bandwidth. All subsequent cells are placed in buckets (potentially in a different group) to reflect the new bandwidth. Cells are scheduled for transmission as in the framework described above.
According to another aspect of the present invention, a scheduler provides for efficient transmission of a sequence of cells forming a frame. The sequence of cells includes a first cell of the frame, a last cell, and several intermediate cells. A scheduler waits until the last cell is received before transmitting any of the sequence of cells.
Such waiting in an intermediate switch of a connection path provides for efficient transmission of frames on ATM networks because the buffering requirements in subsequent switches in the connection path may be minimized. In addition, the drop policy may be simplified because all cells can be dropped if desired.
Waiting for the last cell of a frame provides other advantages as well. A switch with such a waiting can be extended to support ports (e.g., a port interfacing to an Ethernet network) which require the transmission of a complete frame. Transmission of a complete frame is required in switches which provide interface to networks (or systems) which operate using frame as a basic unit of transmission. Accordingly, it may be easier to extend any switch in a network as an end-switch interfacing with networks using a frame as a unit of transmission.
Also, the transmission of frames also is integrated with the framework described above. The first cell of a frame is placed in a scheduling bucket only after the last cell is received, and all the cells for the frame are transmitted in successive turns allocated to the bucket group immediately after the first cell is scheduled for transmission.
Even though cells of a frame are transmitted in quick succession, fairness can be maintained at a macro level among connections serving frames by adjusting the bucket gap taking into account the bandwidth requested for the connection and the number of cells transmitted for a frame. That is, the first cell of the next frame can be placed a number of buckets farther from the current bucket proportional to the number of cells transmitted divided by the desired bandwidth for the connection. In an alternate embodiment, the bucket gap is made proportional to the average intercell time of the connection and the number of cells transmitted is ignored to save processing time.
Therefore, the present invention provides for an integrated scheme to schedule cells fairly while providing for shaping, transmission of frame, and dynamic change of shaping rates and bandwidths.
The present invention supports shaping while minimizing storing and processing requirements, particularly during periods of congestion in a switch. This is because of the recognition that the conformance time of previous cells need not be used when there is substantial backlog in transmitting cells which have already arrived on connections.
Also, the present invention allows the shaping rate of a shaped connection to be dynamically changed. This is achieved by computing conformance time of unscheduled cells using a intercell time corresponding to the new shaping rate.
Further, the present invention allows the desired bandwidth of non-shaped connections to be dynamically changed. This is achieved by computing the intercell time corresponding to the new desired bandwidth, and placing subsequent cells in buckets corresponding to the computed intercell time.
In addition, the present invention allows efficient transmission of a sequence of cells forming a frame. This is accomplished by buffering all of the sequence of cells until the last cell of the sequence is received in the switch, and then scheduling for transmission the cells for transmission in successive transmission turns provided to the bucket group.
Also, fairness is maintained even though the sequence of cells forming a frame are transmitted in quick succession because the subsequent frame is scheduled for transmission taking into account the desired bandwidth for the connection and the number of cells transmitted for a frame.
Further features and advantages of the invention, as well as the structure and operation of various embodiments of the invention, are described in detail below with reference to the accompanying drawings. In the drawings, like reference numbers generally indicate identical, functionally similar, and/or structurally similar elements. The drawing in which an element first appears is indicated by the leftmost digit(s) in the corresponding reference number.